<!DOCTYPE html>
<html lang="en">
<head>
        <meta charset="utf-8" />
        <title>Part.2.D.4-recursion</title>
        <link rel="stylesheet" href="/theme/css/main.css" />

        <!--[if IE]>
            <script src="http://html5shiv.googlecode.com/svn/trunk/html5.js"></script>
        <![endif]-->
</head>

<body id="index" class="home">
        <header id="banner" class="body">
                <h1><a href="/">PythonTutorials </a></h1>
                <nav><ul>
                    <li><a href="/category/cpp.html">cpp</a></li>
                    <li class="active"><a href="/category/python.html">python</a></li>
                </ul>
                </nav>
        </header><!-- /#banner -->
<section id="content" class="body">
  <article>
    <header>
      <h1 class="entry-title">
        <a href="/Part.2.D.4-recursion.html" rel="bookmark"
           title="Permalink to Part.2.D.4-recursion">Part.2.D.4-recursion</a></h1>
    </header>

    <div class="entry-content">
<footer class="post-info">
        <span>Mon 06 April 2020</span>
<span>| tags: <a href="/tag/python.html">python</a><a href="/tag/progarmming.html">progarmming</a><a href="/tag/excel.html">Excel</a></span>
</footer><!-- /.post-info -->      <h1>递归函数</h1>
<h2>递归（Recursion）</h2>
<p>在函数中有个理解门槛比较高的概念：<strong>递归函数</strong>（Recursive Functions）—— 那些<strong>在自身内部调用自身的函数</strong>。说起来都比较拗口。</p>
<p>先看一个例子，我们想要有个能够计算 <code>n</code> 的<em>阶乘</em>（factorial）<code>n!</code> 的函数，<code>f()</code>，规则如下：</p>
<blockquote>
<ul>
<li><code>n! = n × (n-1) × (n-2)... × 1</code></li>
<li>即，<code>n! = n × (n-1)!</code></li>
<li>且，<code>n &gt;= 1</code></li>
</ul>
<p><strong>注意</strong>：以上是数学表达，不是程序，所以，<code>=</code> 在这一小段中是 “<em>等于</em>” 的意思，<strong>不是程序语言中的赋值符号</strong>。</p>
</blockquote>
<p>于是，计算 <code>f(n)</code> 的 Python 程序如下：</p>
<div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">f</span><span class="p">(</span><span class="n">n</span><span class="p">):</span>
    <span class="k">if</span> <span class="n">n</span> <span class="o">==</span> <span class="mi">1</span><span class="p">:</span>
        <span class="k">return</span> <span class="mi">1</span>
    <span class="k">else</span><span class="p">:</span>
        <span class="k">return</span> <span class="n">n</span> <span class="o">*</span> <span class="n">f</span><span class="p">(</span><span class="n">n</span><span class="o">-</span><span class="mi">1</span><span class="p">)</span>

<span class="k">print</span><span class="p">(</span><span class="n">f</span><span class="p">(</span><span class="mi">5</span><span class="p">))</span>
</pre></div>


<div class="highlight"><pre><span></span>120
</pre></div>


<h2>递归函数的执行过程</h2>
<p>以 factorial(5) 为例，让我们看看程序的流程：</p>
<p><img alt="123" src="https://raw.githubusercontent.com/selfteaching/the-craft-of-selfteaching/master/images/recursive-function-call.png?raw=true"></p>
<p>当 f(5) 被调用之后，函数开始运行……
* 因为 <code>5 &gt; 1</code>，所以，在计算 <code>n * f(n-1)</code> 的时候要再次调用自己 <code>f(4)</code>；所以必须等待 <code>f(4)</code> 的值返回；
* 因为 <code>4 &gt; 1</code>，所以，在计算 <code>n * f(n-1)</code> 的时候要再次调用自己 <code>f(3)</code>；所以必须等待 <code>f(3)</code> 的值返回；
* 因为 <code>3 &gt; 1</code>，所以，在计算 <code>n * f(n-1)</code> 的时候要再次调用自己 <code>f(2)</code>；所以必须等待 <code>f(2)</code> 的值返回；
* 因为 <code>2 &gt; 1</code>，所以，在计算 <code>n * f(n-1)</code> 的时候要再次调用自己 <code>f(1)</code>；所以必须等待 <code>f(1)</code> 的值返回；
* 因为 <code>1 == 1</code>，所以，这时候不会再次调用 <code>f()</code> 了，于是递归结束，开始返回，这次返回的是 <code>1</code>；
* 下一步返回的是 <code>2 * 1</code>；
* 下一步返回的是 <code>3 * 2</code>；
* 下一步返回的是 <code>4 * 6</code>；
* 下一步返回的是 <code>5 * 24</code> —— 至此，外部调用 <code>f(5)</code> 的最终返回值是 <code>120</code>……</p>
<p>加上一些输出语句之后，能更清楚地看到大概的执行流程：</p>
<div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">f</span><span class="p">(</span><span class="n">n</span><span class="p">):</span>
    <span class="k">print</span><span class="p">(</span><span class="s1">&#39;</span><span class="se">\t</span><span class="s1">n =&#39;</span><span class="p">,</span> <span class="n">n</span><span class="p">)</span>
    <span class="k">if</span> <span class="n">n</span> <span class="o">==</span> <span class="mi">1</span><span class="p">:</span>
        <span class="k">print</span><span class="p">(</span><span class="s1">&#39;Returning...&#39;</span><span class="p">)</span>
        <span class="k">print</span><span class="p">(</span><span class="s1">&#39;</span><span class="se">\t</span><span class="s1">n =&#39;</span><span class="p">,</span> <span class="n">n</span><span class="p">,</span> <span class="s1">&#39;return:&#39;</span><span class="p">,</span> <span class="mi">1</span><span class="p">)</span>
        <span class="k">return</span> <span class="mi">1</span>
    <span class="k">else</span><span class="p">:</span>
        <span class="n">r</span> <span class="o">=</span> <span class="n">n</span> <span class="o">*</span> <span class="n">f</span><span class="p">(</span><span class="n">n</span><span class="o">-</span><span class="mi">1</span><span class="p">)</span>
        <span class="k">print</span><span class="p">(</span><span class="s1">&#39;</span><span class="se">\t</span><span class="s1">n =&#39;</span><span class="p">,</span> <span class="n">n</span><span class="p">,</span> <span class="s1">&#39;return:&#39;</span><span class="p">,</span> <span class="n">r</span><span class="p">)</span>
        <span class="k">return</span> <span class="n">r</span>

<span class="k">print</span><span class="p">(</span><span class="s1">&#39;Call f(5)...&#39;</span><span class="p">)</span>
<span class="k">print</span><span class="p">(</span><span class="s1">&#39;Get out of f(n), and f(5) =&#39;</span><span class="p">,</span> <span class="n">f</span><span class="p">(</span><span class="mi">5</span><span class="p">))</span>
</pre></div>


<div class="highlight"><pre><span></span>Call f(5)...
    n = 5
    n = 4
    n = 3
    n = 2
    n = 1
Returning...
    n = 1 return: 1
    n = 2 return: 2
    n = 3 return: 6
    n = 4 return: 24
    n = 5 return: 120
Get out of f(n), and f(5) = 120
</pre></div>


<p>有点烧脑…… 不过，分为几个层面去逐个突破，你会发现它真的很好玩。</p>
<h2>递归的终点</h2>
<p>递归函数在内部必须有一个能够让自己停止调用自己的方式，否则永远循环下去了……</p>
<p>其实，我们所有人很小就见过递归应用，只不过，那时候不知道那就是递归而已。听过那个无聊的故事罢？</p>
<blockquote>
<p>山上有座庙，庙里有个和尚，和尚讲故事，说……</p>
<blockquote>
<p>山上有座庙，庙里有个和尚，和尚讲故事，说……</p>
<blockquote>
<p>山上有座庙，庙里有个和尚，和尚讲故事，说……</p>
</blockquote>
</blockquote>
</blockquote>
<p>写成 Python 程序大概是这样：</p>
<div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">a_monk_telling_story</span><span class="p">():</span>
    <span class="k">print</span><span class="p">(</span><span class="s1">&#39;山上有座庙，庙里有个和尚，和尚讲故事，他说…… &#39;</span><span class="p">)</span>
    <span class="k">return</span> <span class="n">a_monk_telling_story</span><span class="p">()</span>

<span class="n">a_monk_telling_story</span><span class="p">()</span>
</pre></div>


<p>这是个<em>无限循环</em>的递归，因为这个函数里<em>没有设置中止自我调用的条件</em>。无限循环还有个不好听的名字，叫做 “死循环”。</p>
<p>在著名的电影<strong>盗梦空间</strong>（<em>2010</em>）里，从整体结构上来看，“入梦” 也是个 “递归函数”。只不过，这个函数和 <code>a_monk_telling_story()</code> 不一样，它并不是死循环 —— 因为它设定了<em>中止自我调用的条件</em>：</p>
<blockquote>
<p>在电影里，醒过来的条件有两个</p>
<blockquote>
<ul>
<li>一个是在梦里死掉；</li>
<li>一个是在梦里被 kicked 到……</li>
</ul>
</blockquote>
<p>如果这两个条件一直不被满足，那就进入 limbo 状态 —— 其实就跟死循环一样，出不来了……</p>
</blockquote>
<p>为了演示，我把故事情节改变成这样：</p>
<blockquote>
<ul>
<li>入梦，<code>in_dream()</code>，是个递归函数；</li>
<li>入梦之后醒过来的条件有两个：<blockquote>
<ul>
<li>一个是在梦里死掉，<code>dead is True</code>；</li>
<li>一个是在梦里被 kicked，<code>kicked is True</code>……</li>
</ul>
<p>以上两个条件中任意一个被满足，就苏醒……</p>
</blockquote>
</li>
</ul>
</blockquote>
<p>至于为什么会死掉，如何被 kick，我偷懒了一下：管它怎样，管它如何，反正，每个条件被满足的概率是 1/10……（也只有这样，我才能写出一个简短的，能够运行的 “<em>盗梦空间程序</em>”。）</p>
<p>把这个很抽象的故事写成 Python 程序，看看一次入梦之后能睡多少天，大概是这样：</p>
<div class="highlight"><pre><span></span><span class="kn">import</span> <span class="nn">random</span>

<span class="k">def</span> <span class="nf">in_dream</span><span class="p">(</span><span class="n">day</span><span class="o">=</span><span class="mi">0</span><span class="p">,</span> <span class="n">dead</span><span class="o">=</span><span class="bp">False</span><span class="p">,</span> <span class="n">kicked</span><span class="o">=</span><span class="bp">False</span><span class="p">):</span>
    <span class="n">dead</span> <span class="o">=</span> <span class="ow">not</span> <span class="n">random</span><span class="o">.</span><span class="n">randrange</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span><span class="mi">10</span><span class="p">)</span> <span class="c1"># 1/10 probability to be dead</span>
    <span class="n">kicked</span> <span class="o">=</span> <span class="ow">not</span> <span class="n">random</span><span class="o">.</span><span class="n">randrange</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span><span class="mi">10</span><span class="p">)</span> <span class="c1"># 1/10 probability to be kicked</span>
    <span class="n">day</span> <span class="o">+=</span> <span class="mi">1</span>
    <span class="k">print</span><span class="p">(</span><span class="s1">&#39;dead:&#39;</span><span class="p">,</span> <span class="n">dead</span><span class="p">,</span> <span class="s1">&#39;kicked:&#39;</span><span class="p">,</span> <span class="n">kicked</span><span class="p">)</span>

    <span class="k">if</span> <span class="n">dead</span><span class="p">:</span>
        <span class="k">print</span><span class="p">((</span><span class="n">f</span><span class="s2">&quot;I slept {day} days, and was dead to wake up...&quot;</span><span class="p">))</span>
        <span class="k">return</span> <span class="n">day</span>
    <span class="k">elif</span> <span class="n">kicked</span><span class="p">:</span>
        <span class="k">print</span><span class="p">(</span><span class="n">f</span><span class="s2">&quot;I slept {day} days, and was kicked to wake up...&quot;</span><span class="p">)</span>
        <span class="k">return</span> <span class="n">day</span>

    <span class="k">return</span> <span class="n">in_dream</span><span class="p">(</span><span class="n">day</span><span class="p">)</span>

<span class="k">print</span><span class="p">(</span><span class="s1">&#39;The in_dream() function returns:&#39;</span><span class="p">,</span> <span class="n">in_dream</span><span class="p">())</span>
</pre></div>


<div class="highlight"><pre><span></span><span class="n">dead</span><span class="o">:</span> <span class="n">False</span> <span class="n">kicked</span><span class="o">:</span> <span class="n">False</span>
<span class="n">dead</span><span class="o">:</span> <span class="n">False</span> <span class="n">kicked</span><span class="o">:</span> <span class="n">False</span>
<span class="n">dead</span><span class="o">:</span> <span class="n">False</span> <span class="n">kicked</span><span class="o">:</span> <span class="n">False</span>
<span class="n">dead</span><span class="o">:</span> <span class="n">False</span> <span class="n">kicked</span><span class="o">:</span> <span class="n">False</span>
<span class="n">dead</span><span class="o">:</span> <span class="n">False</span> <span class="n">kicked</span><span class="o">:</span> <span class="n">False</span>
<span class="n">dead</span><span class="o">:</span> <span class="n">False</span> <span class="n">kicked</span><span class="o">:</span> <span class="n">False</span>
<span class="n">dead</span><span class="o">:</span> <span class="n">False</span> <span class="n">kicked</span><span class="o">:</span> <span class="n">False</span>
<span class="n">dead</span><span class="o">:</span> <span class="n">True</span> <span class="n">kicked</span><span class="o">:</span> <span class="n">True</span>
<span class="n">I</span> <span class="n">slept</span> <span class="mi">8</span> <span class="n">days</span><span class="o">,</span> <span class="n">and</span> <span class="n">was</span> <span class="n">dead</span> <span class="n">to</span> <span class="n">wake</span> <span class="n">up</span><span class="o">...</span>
<span class="n">The</span> <span class="n">in_dream</span><span class="o">()</span> <span class="kd">function</span> <span class="n">returns</span><span class="o">:</span> <span class="mi">8</span>
</pre></div>


<p>如果疑惑为什么 <code>random.randrange(0,10)</code> 能表示 1/10 的概率，请返回去重新阅读<a href="Part.1.E.2.values-and-their-operators.md">第一部分中关于布尔值的内容</a>。</p>
<p>另外，在 Python 中，若是需要将某个值与 True 或者 False 进行比较，尤其是在条件语句中，推荐写法是（参见 <a href="https://www.python.org/dev/peps/pep-0008/">PEP8</a>）：</p>
<div class="highlight"><pre><span></span><span class="k">if</span> <span class="n">condition</span><span class="p">:</span>
    <span class="k">pass</span>
</pre></div>


<p>就好像上面代码中的 <code>if dead:</code> 一样。</p>
<p>而不是（虽然这么写通常也并不妨碍程序正常运行<a href='#fn1' name='fn1b'><sup>[1]</sup></a>）：</p>
<div class="highlight"><pre><span></span><span class="k">if</span> <span class="n">condition</span> <span class="ow">is</span> <span class="bp">True</span><span class="p">:</span>
    <span class="k">pass</span>
</pre></div>


<p>抑或：</p>
<div class="highlight"><pre><span></span><span class="k">if</span> <span class="n">condition</span> <span class="o">==</span> <span class="bp">True</span><span class="p">:</span>
    <span class="k">pass</span>
</pre></div>


<p>让我们再返回来接着讲递归函数。正常的<strong>递归函数一定有个退出条件</strong>。否则的话，就<em>无限循环</em>下去了…… 下面的程序在执行一会儿之后就会告诉你：<code>RecursionError: maximum recursion depth exceeded</code>（上面那个 “山上庙里讲故事的和尚说” 的程序，真要跑起来，也是这样）：</p>
<div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">x</span><span class="p">(</span><span class="n">n</span><span class="p">):</span>
    <span class="k">return</span> <span class="n">n</span> <span class="o">*</span> <span class="n">x</span><span class="p">(</span><span class="n">n</span><span class="o">-</span><span class="mi">1</span><span class="p">)</span>
<span class="n">x</span><span class="p">(</span><span class="mi">5</span><span class="p">)</span>
</pre></div>


<div class="highlight"><pre><span></span>---------------------------------------------------------------------------

RecursionError                            Traceback (most recent call last)

&lt;ipython-input-3-daa4d33fb39b&gt; in &lt;module&gt;
      1 def x(n):
      2     return n * x(n-1)
----&gt; 3 x(5)

&lt;ipython-input-3-daa4d33fb39b&gt; in x(n)
      1 def x(n):
----&gt; 2     return n * x(n-1)
      3 x(5)

... last 1 frames repeated, from the frame below ...

&lt;ipython-input-3-daa4d33fb39b&gt; in x(n)
      1 def x(n):
----&gt; 2     return n * x(n-1)
      3 x(5)

RecursionError: maximum recursion depth exceeded
</pre></div>


<p>不用深究上面盗梦空间这个程序的其它细节，不过，通过以上三个递归程序 —— 两个很扯淡的例子，一个正经例子 —— 你已经看到了递归函数的共同特征：</p>
<blockquote>
<ol>
<li>在 <code>return</code> 语句中返回的是<em>自身的调用</em>（或者是<em>含有自身的表达式</em>）</li>
<li>为了避免死循环，<em>一定要有至少一个条件</em>下返回的不再是自身调用……</li>
</ol>
</blockquote>
<h2>变量的作用域</h2>
<p>再回来看计算阶乘的程序 —— 这是正经程序。这次我们把程序名写完整，<code>factorial()</code>:</p>
<div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">factorial</span><span class="p">(</span><span class="n">n</span><span class="p">):</span>
    <span class="k">if</span> <span class="n">n</span> <span class="o">==</span> <span class="mi">1</span><span class="p">:</span>
        <span class="k">return</span> <span class="mi">1</span>
    <span class="k">else</span><span class="p">:</span>
        <span class="k">return</span> <span class="n">n</span> <span class="o">*</span> <span class="n">factorial</span><span class="p">(</span><span class="n">n</span><span class="o">-</span><span class="mi">1</span><span class="p">)</span>

<span class="k">print</span><span class="p">(</span><span class="n">factorial</span><span class="p">(</span><span class="mi">5</span><span class="p">))</span>
</pre></div>


<div class="highlight"><pre><span></span>120
</pre></div>


<p>最初的时候，这个函数的执行流程之所以令人迷惑，是因为初学者对<em>变量</em>的<strong>作用域</strong>把握得不够充分。</p>
<p>变量根据作用域，可以分为两种：全局变量（Global Variables）和局部变量（Local Variables）。</p>
<p>可以这样简化理解：</p>
<blockquote>
<ul>
<li>在函数内部被赋值而后使用的，都是<em>局部变量</em>，它们的作用域是<em>局部</em>，无法被函数外的代码调用；</li>
<li>在所有函数之外被赋值而后开始使用的，是<em>全局变量</em>，它们的作用域是<em>全局</em>，在函数内外都可以被调用。</li>
</ul>
</blockquote>
<p>定义如此，但通常程序员们会严格地遵守一条原则：</p>
<blockquote>
<p>在函数内部绝对不调用全局变量。即便是必须改变全局变量，也只能通过函数的返回值在函数外改变全局变量。</p>
</blockquote>
<p>你也必须遵守同样的原则。而这个原则同样可以在日常的工作生活中 “调用”：</p>
<blockquote>
<p>做事的原则：自己的事自己做，别人的事，最多通过自己的产出让他们自己去搞……</p>
</blockquote>
<p>再仔细观察一下以下代码。当一个变量被当做参数传递给一个函数的时候，这个变量本身并不会被函数所改变。比如，<code>a = 5</code>，而后，再把 <code>a</code> 当作参数传递给 <code>f(a)</code> 的时候，这个函数当然应该返回它内部任务完成之后应该传递回来的值，但 <code>a</code> 本身不会被改变。</p>
<div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">factorial</span><span class="p">(</span><span class="n">n</span><span class="p">):</span>
    <span class="k">if</span> <span class="n">n</span> <span class="o">==</span> <span class="mi">1</span><span class="p">:</span>
        <span class="k">return</span> <span class="mi">1</span>
    <span class="k">else</span><span class="p">:</span>
        <span class="k">return</span> <span class="n">n</span> <span class="o">*</span> <span class="n">factorial</span><span class="p">(</span><span class="n">n</span><span class="o">-</span><span class="mi">1</span><span class="p">)</span>

<span class="n">a</span> <span class="o">=</span> <span class="mi">5</span>
<span class="n">b</span> <span class="o">=</span> <span class="n">factorial</span><span class="p">(</span><span class="n">a</span><span class="p">)</span>   <span class="c1"># a 并不会因此改变；</span>
<span class="k">print</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">)</span>
<span class="n">a</span> <span class="o">=</span> <span class="n">factorial</span><span class="p">(</span><span class="n">a</span><span class="p">)</span>   <span class="c1"># 这是你主动为 a 再一次赋值……</span>
<span class="k">print</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">)</span>
</pre></div>


<div class="highlight"><pre><span></span>5 120
120 120
</pre></div>


<p>理解了这一点之后，再看 <code>factorial()</code> 这个递归函数的递归执行过程，你就能明白这个事实：</p>
<blockquote>
<p>在每一次 factorial(n) 被调用的时候，它都会形成一个作用域，<code>n</code> 这个变量作为参数把它的值传递给了函数，<em>但是</em>，<code>n</code> 这个变量本身并不会被改变。</p>
</blockquote>
<p>我们再修改一下上面的代码：</p>
<div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">factorial</span><span class="p">(</span><span class="n">n</span><span class="p">):</span>
    <span class="k">if</span> <span class="n">n</span> <span class="o">==</span> <span class="mi">1</span><span class="p">:</span>
        <span class="k">return</span> <span class="mi">1</span>
    <span class="k">else</span><span class="p">:</span>
        <span class="k">return</span> <span class="n">n</span> <span class="o">*</span> <span class="n">factorial</span><span class="p">(</span><span class="n">n</span><span class="o">-</span><span class="mi">1</span><span class="p">)</span>

<span class="n">n</span> <span class="o">=</span> <span class="mi">5</span>              <span class="c1"># 这一次，这个变量名称是 n</span>
<span class="n">m</span> <span class="o">=</span> <span class="n">factorial</span><span class="p">(</span><span class="n">n</span><span class="p">)</span>   <span class="c1"># n 并不会因此改变；</span>
<span class="k">print</span><span class="p">(</span><span class="n">n</span><span class="p">,</span> <span class="n">m</span><span class="p">)</span>
</pre></div>


<div class="highlight"><pre><span></span>5 120
</pre></div>


<p>在 <code>m = factorial(n)</code> 这一句中，<code>n</code> 被 <code>factorial()</code> 当做参数调用了，但无论函数内部如何操作，并不会改变变量 <code>n</code> 的值。</p>
<p>关键的地方在这里：在函数内部出现的变量 <code>n</code>，和函数外部的变量 <code>n</code> 不是一回事 —— <strong>它们只是名称恰好相同而已</strong>，函数参数定义的时候，用别的名称也没什么区别：</p>
<div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">factorial</span><span class="p">(</span><span class="n">x</span><span class="p">):</span> <span class="c1"># 在这个语句块中出现的变量，都是局部变量</span>
    <span class="k">if</span> <span class="n">x</span> <span class="o">==</span> <span class="mi">1</span><span class="p">:</span>
        <span class="k">return</span> <span class="mi">1</span>
    <span class="k">else</span><span class="p">:</span>
        <span class="k">return</span> <span class="n">x</span> <span class="o">*</span> <span class="n">factorial</span><span class="p">(</span><span class="n">x</span><span class="o">-</span><span class="mi">1</span><span class="p">)</span>

<span class="n">n</span> <span class="o">=</span> <span class="mi">5</span>           <span class="c1"># 这一次，这个变量名称是 n</span>
<span class="n">m</span> <span class="o">=</span> <span class="n">factorial</span><span class="p">(</span><span class="n">n</span><span class="p">)</span>   <span class="c1"># n 并不会因此改变；</span>
<span class="k">print</span><span class="p">(</span><span class="n">n</span><span class="p">,</span> <span class="n">m</span><span class="p">)</span>
<span class="c1"># 这个例子和之前再之前的示例代码有什么区别吗？</span>
<span class="c1"># 本质上没区别，就是变量名称换了而已……</span>
</pre></div>


<div class="highlight"><pre><span></span>5 120
</pre></div>


<p>函数开始执行的时候，<code>x</code> 的值，是由外部代码（即，函数被调用的那一句）传递进来的。即便函数内部的变量名称与外部的变量名称相同，它们也不是同一个变量。</p>
<h2>递归函数三原则</h2>
<p>现在可以小小总结一下了。</p>
<p>一个递归函数，之所以是一个有用、有效的递归函数，是因为它要遵守递归三原则。正如，一个机器人之所以是个合格的机器人，是因为它遵循<a href="https://zh.wikipedia.org/wiki/%E6%9C%BA%E5%99%A8%E4%BA%BA%E4%B8%89%E5%AE%9A%E5%BE%8B">阿西莫夫三铁律</a>（Three Laws of Robotics）一样<a href='#fn2' name='fn2b'><sup>[2]</sup></a>。</p>
<blockquote>
<ol>
<li>根据定义，递归函数必须在内部调用自己；</li>
<li>必须设定一个退出条件；</li>
<li>递归过程中必须能够逐步达到退出条件……</li>
</ol>
</blockquote>
<p>从这个三原则望过去，<code>factorial()</code> 是个合格有效的递归函数，满足第一条，满足第二条，尤其还满足第三条中的 “<em>逐步达到</em>”！</p>
<p>而那个扯淡的盗梦空间递归程序，说实话，不太合格，虽然它满足第一条，也满足第二条，第三条差点蒙混过关：它不是<em>逐步达到</em>，而是<em>不管怎样肯定能达到</em> —— 这明显是两回事…… 原谅它罢，它的作用就是当例子，一次正面的，一次负面的，作为例子算是功成圆满了！</p>
<p>刚开始的时候，初学者好不容易搞明白递归函数究竟是怎么回事之后，就不由自主地想 “我如何才能学会递归式思考呢？” —— 其实吧，这种想法本身可能并不是太正确或者准确。</p>
<p>准确地讲，递归是一种解决问题的方式。当我们需要解决的问题，可以被逐步拆分成很多越来越小的模块，然后每个小模块还都能用同一种算法处理的时候，用递归函数最简洁有效。所以，只不过是在遇到可以用递归函数解决问题的时候，才需要去写递归函数。</p>
<p>从这个意义上来看，递归函数是程序员为了自己方便而使用的，并不是为了计算机方便而使用 —— 计算机么，你给它的任务多一点或者少一点，对它来讲无所谓，反正有电就能运转，它自己又不付电费……</p>
<p>理论上来讲，所有用递归函数能完成的任务，不用递归函数也能完成，只不过代码多一点，啰嗦一点，看起来没有那么优美而已。</p>
<p>还有，递归，不像 “序列类型” 那样，是某个编程语言的特有属性。它其实是一种特殊算法，也是一种编程技巧，任何编程语言，都可以使用递归算法，都可以通过编写递归函数巧妙地解决问题。</p>
<p>但是，学习递归函数本身就很烧脑啊！这才是最大的好事。从迷惑，到不太迷惑，到清楚，到很清楚，再到特别清楚 —— 这是个非常有趣，非常有成就感的过程。</p>
<p>这种过程锻炼的是脑力 —— 在此之后，再遇到大多数人难以理解的东西，你就可以使用这一次积累的经验，应用你已经磨炼过的脑力。有意思。</p>
<p>至此，封面上的那个 “伪代码” 应该很好理解了：</p>
<div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">teach_yourself</span><span class="p">(</span><span class="n">anything</span><span class="p">):</span>
    <span class="k">while</span> <span class="ow">not</span> <span class="n">create</span><span class="p">():</span>
        <span class="n">learn</span><span class="p">()</span>
        <span class="n">practice</span><span class="p">()</span>
    <span class="k">return</span> <span class="n">teach_yourself</span><span class="p">(</span><span class="n">another</span><span class="p">)</span>

<span class="n">teach_yourself</span><span class="p">(</span><span class="n">coding</span><span class="p">)</span>
</pre></div>


<p>自学还真的就是递归函数呢……</p>
<h2>思考与练习</h2>
<p>普林斯顿大学的一个网页，有很多递归的例子</p>
<p>https://introcs.cs.princeton.edu/java/23recursion/</p>
<hr>
<p><strong>脚注</strong></p>
<p><a name='fn1'>[1]</a>：参见 Stackoverflow 上的讨论：<a href="https://stackoverflow.com/questions/27276610/boolean-identity-true-vs-is-true">Boolean identity == True vs is True</a></p>
<p><a href='#fn1b'><small>↑Back to Content↑</small></a></p>
<p><a name='fn2'>[2]</a>：关于<a href="https://zh.wikipedia.org/wiki/%E6%9C%BA%E5%99%A8%E4%BA%BA%E4%B8%89%E5%AE%9A%E5%BE%8B">阿西莫夫三铁律</a>（Three Laws of Robotics）的类比，来自著名的 Python 教程，<a href="http://greenteapress.com/thinkpython2/html/index.html">Think Python: How to Think Like a Computer Scientist</a></p>
<p><a href='#fn2b'><small>↑Back to Content↑</small></p>
    </div><!-- /.entry-content -->

  </article>
</section>
        <section id="extras" class="body">
                <div class="blogroll">
                        <h2>blogroll</h2>
                        <ul>
                            <li><a href="http://getpelican.com/">Pelican</a></li>
                            <li><a href="http://python.org/">Python.org</a></li>
                            <li><a href="http://jinja.pocoo.org/">Jinja2</a></li>
                            <li><a href="#">You can modify those links in your config file</a></li>
                        </ul>
                </div><!-- /.blogroll -->
                <div class="social">
                        <h2>social</h2>
                        <ul>

                            <li><a href="#">You can add links in your config file</a></li>
                            <li><a href="#">Another social link</a></li>
                        </ul>
                </div><!-- /.social -->
        </section><!-- /#extras -->

        <footer id="contentinfo" class="body">
                <p>Powered by <a href="http://www.maxiaoan.com/">Maxiaoan</a></p>
        </footer><!-- /#contentinfo -->

</body>
</html>